《剑指offer》 19.正则表达式匹配

note:两个字符串匹配的问题,经典的解法就是使用二维dp数组进行动态规划求解,因为显然字符串匹配就是一个可以分解为小问题、依赖小问题来解决大问题的问题。

题目描述

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符,而’*‘表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但与”aa.a”和”ab*a”均不匹配。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母以及字符 ‘.’ 和’*‘,无连续的 ‘*’。

方法一: 二维动态规划

思路

两个字符串的匹配问题,可以转换为二维动态规划问题。

两个字符串的匹配是非常复杂的,但是单个的字符匹配是简单的,动态规划解决字符串匹配的问题的关键就是考虑到,我们可以转化的小问题,是匹配两个字符串的各个子串。

我们考虑使用dp[m][n]数组来表示动态规划存储的匹配方案,$dp[i][j]$表示$s$前$i$个字符和$p$前$j$个字符是否可以匹配。

接下来我们分情况进行讨论

  • $p$的第$j$ 个字符是字母。由于$s$中都是字母,那么很显然如果当前两个字符相同,前面的子串可以匹配,那自然新的子串也可以进行匹配。这种情况的状态转移方程非常简单:

  • $p$的第$j$个字符是’.’。由于’.’可以匹配任何一个字符,那它的转移方程更为简单:

  • $p$的第$j$个字符是’*‘。这种情况就比较复杂了,因为’*‘的匹配规则是“它前面的字符可以出现任意次(含0次)”也就是说$p$第$j$个位置出现*号时我们就要考虑第$j-1$个字符的情况。此时我们可以列出来该字符出现若干次时的状态转移

    • 出现0次:$dp[i][j] = dp[i][j-2]$。含义就是既然我第$j-1$个字符没有出现,那么我$s$字符串中的第$i$个字符就不应该和我第$j-1$个字符进行匹配,而应该和再往前一个字符匹配,也就是第$j-2$个字符。
    • 出现1次并且和$s$中的第$i$个元素成功匹配:$dp[i][j]=dp[i-1][j-2]$,向前匹配
    • 出现2次并且和$s$中的第$i$个、第$i-1$个元素成功匹配:$dp[i][j] = dp[i-2][j-2]$,继续向前匹配
    • ·········

    根据这个过程,我们可以得出一个状态转移方程

    理解为当$p$中第$j-1$个元素不等于$s$中第$i$个元素时(匹配失败),就将第$j-1$个元素视作出现0次处理。将$s$中的第$i$个元素和$p$中的第$j-2$个元素对比,如果匹配成功,则考虑多种情况,既有可能虽然匹配成功,但是该元素不一定要出现(0次出现),也有可能该次出现有效,往前溯源看前面是否相同。

最后的话我们总结三种状态转移方程,得到一个整体的转移方程如下:

match(x,y)是我们做的匹配过程,为了提高程序的复用性,我们可以写成c++11标准中的lambda表达式,lambda表达式用于定义并创建匿名的函数对象,以简化编程。使用格式如下:

1
2
3
[函数对象参数] (操作符重载函数参数) mutable  ->返回类型  { 
函数体
};

具体介绍和使用我后面会写一篇额外的博客,这儿就不赘述了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(),n=p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1));

auto match = [&](int x,int y){
if(x==0)
return false;
if(p[y-1]=='.')
return true;
else
return s[x-1]==p[y-1];
};

dp[0][0] = true; // 长度为0的两个子串匹配必然匹配得上
for(int i=0;i<=m;i++){ //s字符串从零匹配
for(int j=1;j<=n;j++){ //p字符串考虑从1开始,因为*号不可能出现在0位置
if(p[j-1]=='*'){
dp[i][j] = dp[i][j-2]; // 加入j-2的位置的元素出现为0次。
if(match(i,j-1)){
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}else{
if(match(i,j)){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[m][n];

}
};

复杂度分析

  • 时间复杂度$O(mn)$。m、n分别为字符串长度
  • 空间复杂度$O(mn)$。dp数组的大小为m*n